package com.lzy.tricbuild3_ac;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class AcTric {

	private AcNode root = new AcNode('/'); // 存储无意义字符

	// 往Trie树中插入一个字符串
	public void insert(char[] text) { // 例如：hello
		AcNode p = root;
		// 遍历插入的字符串
		for (int i = 0; i < text.length; ++i) {
			// 获取遍历的字符
			int index = text[i] - 'a'; // 找到子节点数组下标
			if (p.children[index] == null) { // 如果对应的节点下标为空，说明当前没有该下标长度前的敏感词。例如现在是hel，则表示没有hel敏感词
				// 赋值
				AcNode newNode = new AcNode(text[i]);
				p.children[index] = newNode;

			}
			p = p.children[index];

		}
		p.length = text.length;
		p.isEndingChar = true;  // 当前为最后一个字符串，将标识设置为true
	}

	/**
	 *                '/'
	 *          'h'   'e'   'a'
	 *       'e'      'l'   'h'
	 *     'l'        'l'   'e'
	 *   'l' 'o'            'l'
	 * 'o'                  'l'
	 *                      'o'
	 * @param args
	 */
	public static void main(String[] args) {
		AcTric acTric = new AcTric();

		acTric.insert("hellohellohellohellohellohellohellohellohellohellohellohellohellohellohello".toCharArray());
		acTric.insert("heoheoheoheoheoheoheoheoheoheoheoheoheoheoheoheoheoheoheoheoheoheoheoheoheo".toCharArray());
		acTric.insert("elloelloelloelloelloelloelloelloelloelloelloelloelloelloelloelloelloelloello".toCharArray());
		acTric.insert("ahelloahelloahelloahelloahelloahelloahelloahelloahelloahelloahelloahelloahello".toCharArray());

		acTric.buildFailurePointer();

		acTric.match("joajoejoaijfoeifjapojfpojapojsdpofjapwojefopjsapofjwaopejfpawojahelloahelloahelloahelloahelloahelloahelloahelloahelloahelloahelloahelloahelloadjfajdpaojfpaojfffjsdlkjfalkahelloahelloahelloahelloahelloahelloahelloahelloahelloahelloahelloahelloahellokalsdkfkald".toCharArray());

	}

	// 构建失败指针
	public void buildFailurePointer() {
		Queue<AcNode> queue = new LinkedList<>();
		root.fail = null;
		queue.add(root);
		while (!queue.isEmpty()) {
			AcNode p = queue.remove();   // p当前需要寻找的失败指针
			for (int i = 0; i < 26; ++i) { // 遍历所有子节点。
				AcNode pc = p.children[i];
				if (pc == null) continue;
				if (p == root) {
					pc.fail = root;
				} else {
					AcNode q = p.fail;  // 父类的失败指针
					while (q != null) {  // 寻找上一级的所在
						AcNode qc = q.children[pc.data - 'a'];  // 父类同级的失败指向。
						if (qc != null) {
							pc.fail = qc;
							break;
						}
						q = q.fail;
					}
					if (q == null) {
						pc.fail = root;
					}
				}
				queue.add(pc);
			}
		}
	}


	// 匹配字串
	public List<String> match(char[] text) { // text是主串
		String str = new String(text);
		List<String> ans = new ArrayList<>();

		int n = text.length;
		AcNode p = root;
		for (int i = 0; i < n; ++i) {
			int idx = text[i] - 'a';
			while (p.children[idx] == null && p != root) {
				p = p.fail; // 失败指针发挥作用的地方
			}
			p = p.children[idx];
			if (p == null) p = root; // 如果没有匹配的，从root开始重新匹配
			AcNode tmp = p;
			while (tmp != root) { // 打印出可以匹配的模式串
				if (tmp.isEndingChar == true) {
					int pos = i-tmp.length+1;
//					System.out.println("匹配起始下标" + pos + "; 长度" + tmp.length);
					ans.add(str.substring(pos, pos+ tmp.length));
				}
				tmp = tmp.fail;
			}
		}

		return ans;
	}
}
